package cg.studio.algorithm.route;

import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**********************
 * There are potential exception cases: this implementation can't handle these cases.
 * 1. the route is broken: A->B, C->D 
 * 2. the route is a circle, and can't figure out start or end: A->B, B->C, C->A 
 * 3. the route includes a circle, and in fact we can figure out the start and end
 *   3.1 A->B, B->C, C->D, D->B: in this case, start is A, end is B 
 *   3.2 A->B, B->C, C->D, D->B, B->F: in this case, start is A, end is F 
 *   3.3 A->B, B->C, C->B, B->C: start is A, end is C, and edge duplicated 
 **********************/
/**
 * note: Integer is a immutable class?
 * @author brightchen
 *
 */
public class FlightRoute
{
  public static List< String > sortFlight( String[][] flights ) throws BreakRouteException, LoopRouteException
  {
    if ( flights == null || flights.length == 0 )
      return Collections.emptyList();

    final int flightCount = flights.length;
    Map< String, String > fromToMap = new HashMap< String, String >();
    Map< String, String > toFromMap = new HashMap< String, String >();

    for ( String[] oneFlight : flights )
    {
      if ( oneFlight[0].equalsIgnoreCase( oneFlight[1] ) )
        throw new IllegalArgumentException( "The from and to city are same: " + oneFlight[0] );
      {
        String to = fromToMap.get( oneFlight[0] );
        if( to != null )
          throw new LoopRouteException( "Start from city : " + oneFlight[0] + " has two distination: " + to + " and " + oneFlight[1] );
        fromToMap.put( oneFlight[0], oneFlight[1] );
      }
      {
        String from = toFromMap.get( oneFlight[1] );
        if( from != null )
          throw new LoopRouteException( "End to city : " + oneFlight[1] + " has two start: " + from + " and " + oneFlight[0] );        
        toFromMap.put( oneFlight[1], oneFlight[0] );
      }
    }

    List< String > sortedCities = new LinkedList< String >();

    {
      String fromCity = fromToMap.keySet().iterator().next();

      while ( true )
      {
        String toCity = fromToMap.get( fromCity );

        if ( toCity == null )
          break;
        sortedCities.add( toCity );
        toCity = fromCity;
      }
    }

    String toCity = sortedCities.get( 0 );
    while ( true )
    {
      String fromCity = toFromMap.get( toCity );

      if ( fromCity == null )
        break;
      sortedCities.add( 0, fromCity );
      fromCity = toCity;
    }

    if ( sortedCities.size() < flights.length )
      throw new BreakRouteException();

    return sortedCities;
  }

}
